QUnit.module('FenwickTree', () =>
{
    QUnit.test('should create empty fenwick tree of correct size', (assert) =>
    {
        const tree1 = new ds.FenwickTree(5);
        assert.deepEqual(tree1.treeArray.length, 5 + 1);

        for (let i = 0; i < 5; i += 1)
        {
            assert.deepEqual(tree1.treeArray[i], 0);
        }

        const tree2 = new ds.FenwickTree(50);
        assert.deepEqual(tree2.treeArray.length, 50 + 1);
    });

    QUnit.test('should create correct fenwick tree', (assert) =>
    {
        const inputArray = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2, 3];

        const tree = new ds.FenwickTree(inputArray.length);
        assert.deepEqual(tree.treeArray.length, inputArray.length + 1);

        inputArray.forEach((value, index) =>
        {
            tree.increase(index + 1, value);
        });

        assert.deepEqual(tree.treeArray, [0, 3, 5, -1, 10, 5, 9, -3, 19, 7, 9, 3]);

        assert.deepEqual(tree.query(1), 3);
        assert.deepEqual(tree.query(2), 5);
        assert.deepEqual(tree.query(3), 4);
        assert.deepEqual(tree.query(4), 10);
        assert.deepEqual(tree.query(5), 15);
        assert.deepEqual(tree.query(6), 19);
        assert.deepEqual(tree.query(7), 16);
        assert.deepEqual(tree.query(8), 19);
        assert.deepEqual(tree.query(9), 26);
        assert.deepEqual(tree.query(10), 28);
        assert.deepEqual(tree.query(11), 31);

        assert.deepEqual(tree.queryRange(1, 1), 3);
        assert.deepEqual(tree.queryRange(1, 2), 5);
        assert.deepEqual(tree.queryRange(2, 4), 7);
        assert.deepEqual(tree.queryRange(6, 9), 11);

        tree.increase(3, 1);

        assert.deepEqual(tree.query(1), 3);
        assert.deepEqual(tree.query(2), 5);
        assert.deepEqual(tree.query(3), 5);
        assert.deepEqual(tree.query(4), 11);
        assert.deepEqual(tree.query(5), 16);
        assert.deepEqual(tree.query(6), 20);
        assert.deepEqual(tree.query(7), 17);
        assert.deepEqual(tree.query(8), 20);
        assert.deepEqual(tree.query(9), 27);
        assert.deepEqual(tree.query(10), 29);
        assert.deepEqual(tree.query(11), 32);

        assert.deepEqual(tree.queryRange(1, 1), 3);
        assert.deepEqual(tree.queryRange(1, 2), 5);
        assert.deepEqual(tree.queryRange(2, 4), 8);
        assert.deepEqual(tree.queryRange(6, 9), 11);
    });

    QUnit.test('should correctly execute queries', (assert) =>
    {
        const tree = new ds.FenwickTree(5);

        tree.increase(1, 4);
        tree.increase(3, 7);

        assert.deepEqual(tree.query(1), 4);
        assert.deepEqual(tree.query(3), 11);
        assert.deepEqual(tree.query(5), 11);
        assert.deepEqual(tree.queryRange(2, 3), 7);

        tree.increase(2, 5);
        assert.deepEqual(tree.query(5), 16);

        tree.increase(1, 3);
        assert.deepEqual(tree.queryRange(1, 1), 7);
        assert.deepEqual(tree.query(5), 19);
        assert.deepEqual(tree.queryRange(1, 5), 19);
    });

    QUnit.test('should throw exceptions', (assert) =>
    {
        const tree = new ds.FenwickTree(5);

        const increaseAtInvalidLowIndex = () =>
        {
            tree.increase(0, 1);
        };

        const increaseAtInvalidHighIndex = () =>
        {
            tree.increase(10, 1);
        };

        const queryInvalidLowIndex = () =>
        {
            tree.query(0);
        };

        const queryInvalidHighIndex = () =>
        {
            tree.query(10);
        };

        const rangeQueryInvalidIndex = () =>
        {
            tree.queryRange(3, 2);
        };

        var error0 = false;
        var error1 = false;
        var error2 = false;
        var error3 = false;
        var error4 = false;
        try
        {
            increaseAtInvalidLowIndex();
        } catch (error)
        {
            error0 = true;
        }
        try
        {
            increaseAtInvalidHighIndex();
        } catch (error)
        {
            error1 = true;
        }
        try
        {
            queryInvalidLowIndex();
        } catch (error)
        {
            error2 = true;
        }
        try
        {
            queryInvalidHighIndex();
        } catch (error)
        {
            error3 = true;
        }
        try
        {
            rangeQueryInvalidIndex();
        } catch (error)
        {
            error4 = true;
        }

        assert.deepEqual(error0, true);
        assert.deepEqual(error1, true);
        assert.deepEqual(error2, true);
        assert.deepEqual(error3, true);
        assert.deepEqual(error4, true);
    });
});
